#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    """
    @param nums: A list of integers
    @return: A list of integers
    """
    def nextPermutation(self, nums):
        '''
        [1, 2, 4, 3] ------> [1,2, 3, 4]
        [1, 3, 2, 1] ------> [1, 3, 1, 2]
        '''
        # self.origin = sorted(nums)
        self.nums = nums
        self.n = len(nums)

        # ret = self.next(0)
        ret = self.inverse_find()
        if ret:
            remain_next, idx = ret
            return self.nums[0:idx] + remain_next
        else:
            return list(reversed(nums))     # 直接反序返回

    def next(self, idx):
        '''
            方法1: 递归
            先考虑不重复, 后考虑重复
        '''
        if idx == self.n:
            return None

        remain_next_and_idx = self.next(idx+1)
        # if remain_next:
        #     # 拼接 或者 直接返回 索引和remain_next: 最上层拼接
        #     print('remain_next %s' % remain_next)
        #     return [self.nums[idx]] + remain_next
        if remain_next_and_idx:
            # 拼接 或者 直接返回 索引和remain_next: 最上层拼接
            return remain_next_and_idx
        else:
            ''' 从idx剩下的数字排序: 选择比当前大的数. 取出来, 剩下的正序
                如果当前数字最大: return None
            '''
            cur_ele = self.nums[idx]
            remains = self.nums[idx:]
            remain_max_ele = max(remains)
            if cur_ele == remain_max_ele:
                return None

            return self.make_next_remains(remains), idx

    def inverse_find(self):
        '''
            方法2: 非递归
        '''
        for i in range(self.n-2, -1, -1):
            if self.nums[i+1] > self.nums[i]:
                return self.make_next_remains(self.nums[i:]), i

        return None

    def make_next_remains(self, remains):
        assert remains
        cur_ele = remains[0]
        remains.sort()

        next_idx, next_ele = self.sorted_next_ele(remains, cur_ele)
        assert next_idx and next_ele

        del remains[next_idx]
        return [next_ele] + remains

    def sorted_next_ele(self, l, value):
        # NOTE: 如果有相同元素也要考虑
        for i, v in enumerate(l):
            if v > value:
                return i, v

        return -1, None


def main():
    print("start main")
    s = Solution()
    ret = s.nextPermutation([1,2,3, 4])
    ret = s.nextPermutation([4,3,2,1])
    ret = s.nextPermutation([1 ,3, 2, 3])
    print(ret)

if __name__ == "__main__":
    main()
